package com.mxw.算法之美.a14字典树;


/**
 * @author Administrator
 * @create 2024/8/6 10:57
 */
public class TrieTree {

    /**
     * 解决在一组字符串集合中快速查找某个字符串的问题
     * <p>
     * 本质：利用字符串之间的公共前缀，将重复的前缀合并在一起
     * 结构：根节点不包含任何信息，每个节点代表一个字符串中的字符，从根节点到某一节点，代表从根节点到该节点组成的字符串
     */

    class TrieNode {
        char data;

        TrieNode[] children = new TrieNode[26];

        boolean isEndingChar = false;


        public TrieNode(char value) {
            this.data = value;
        }

    }

    // 存放无意义字符，根节点
    public TrieNode root = new TrieNode('/');

    // 往字典树中插入一个字符串
    public void insert(char[] text) {
        TrieNode p = root;

        for (int i = 0; i < text.length; i++) {
            int index = text[i] - 'a';
            if (p.children[index] == null) {
                TrieNode newNode = new TrieNode(text[i]);
                p.children[index] = newNode;
            }
            p = p.children[index];
        }

        p.isEndingChar = true;
    }

    public boolean search(char[] pattern) {
        TrieNode p = root;

        for (int i = 0; i < pattern.length; i++) {
            int index = pattern[i] - 'a';
            if (p.children[index] == null) {
                // 不存在
                return false;
            }
            p = p.children[index];
        }
        if (p.isEndingChar==false){
            // 不能完全匹配，只是前缀
            return false;
        }else{
            // 找到pattern
            return true;
        }
    }

}
